In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, graph operations are
operations which produce new
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
s from initial ones. They include both
unary (one input) and
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
(two input) operations.
Unary operations
Unary operations create a new graph from a single initial graph.
Elementary operations
Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices,
edge contraction
In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex ide ...
, etc.
The
graph edit distance In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs.
The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983.
A ...
between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.
Advanced operations
Advanced operations create a new graph from initial one by a complex changes, such as:
*
transpose graph
In the mathematical and algorithmic study of graph theory, the converse, transpose or reverse, entry 2.24 of a directed graph is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of th ...
;
*
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
;
*
line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
;
*
graph minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
;
*
graph rewriting
In computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also ...
;
*
power of graph
In graph theory, a branch of mathematics, the th power of an undirected graph is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in is at most . Powers of graphs are referred to ...
;
*
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-lo ...
;
*
medial graph
In the mathematical discipline of graph theory, the medial graph of plane graph ''G'' is another graph ''M(G)'' that represents the adjacencies between edges in the faces of ''G''. Medial graphs were introduced in 1922 by Ernst Steinitz to study ...
;
*
quotient graph In graph theory, a quotient graph ''Q'' of a graph ''G'' is a graph whose vertices are blocks of a partition of the vertices of ''G'' and where block ''B'' is adjacent to block ''C'' if some vertex in ''B'' is adjacent to some vertex in ''C'' with ...
;
*
Y-Δ transform
The Y-Δ transform, also written wye-delta and also known by many other names, is a mathematical technique to simplify the analysis of an electrical network. The name derives from the shapes of the circuit diagrams, which look respectively like t ...
;
*
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic ...
.
Binary operations
Binary operations create a new graph from two initial graphs and , such as:
* graph union: . There are two definitions. In the most common one, the
disjoint union of graphs
In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph.
It is analogous to the disjoint union of sets, and is constructed by making the vertex set of the res ...
, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
in mathematics) the union of two graphs is defined as the graph .
* graph intersection: ;
* graph join: graph with all the edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation (for unlabelled graphs);
[
* ]graph products
In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties:
* The vertex set of is the Cartesian product , where and are t ...
based on the cartesian product of the vertex sets:
** cartesian graph product: it is a commutative and associative operation (for unlabelled graphs),[ Harary, F. ''Graph Theory''. Reading, MA: Addison-Wesley, 1994.]
** lexicographic graph product (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation,[
** strong graph product: it is a commutative and associative operation (for unlabelled graphs),
** tensor graph product (or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product): it is a commutative and associative operation (for unlabelled graphs),
** zig-zag graph product;
* graph product based on other products:
** rooted graph product: it is an associative operation (for unlabelled but rooted graphs),
** corona graph product: it is a non-commutative operation;]Hajós construction
In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.
The construction
Let ...
.
Notes
{{DEFAULTSORT:Graph Operations